class Node {
    public int data;
    public Node next;
    public Node(int data){
        this.data=data;
    }
}
public class List {
    public Node head;
    public Node Containslist(){
        if(this.head==null){
            return null;
        }
        Node slow=this.head;
        Node fast=this.head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}
/**删除链表的节点
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//class Solution {
//    public ListNode deleteNode(ListNode head, int val) {
//        if(head==null){
//            return head;
//        }
//        ListNode newhead=new ListNode(-1);
//        newhead.next=head;
//        ListNode cur=newhead;
//        while(cur.next!=null){
//            if(cur.next.val==val){
//                cur.next=cur.next.next;
//            }
//            else{
//                cur=cur.next;
//            }
//        }
//        return newhead.next;
//    }
//}









/**反转链表

 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        if(head==null||head.next==null){
//            return head;
//        }
//        ListNode perv=null;
//        ListNode cur=head;
//        while(cur!=null){
//            ListNode curnext=cur.next;
//            cur.next=perv;
//            perv=cur;
//            cur=curnext;
//        }
//        return perv;
//    }
//}













/**二进制链表转整数
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public int getDecimalValue(ListNode head) {
//        int count=0;
//        while(head!=null){
//            count=count*2+head.val;
//            head=head.next;
//        }
//        return count;
//    }
//}









/**移除链表元素
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode removeElements(ListNode head, int val) {
//        if(head==null){
//            return head;
//        }
//        ListNode newhead=new ListNode(-1);
//        newhead.next=head;
//        ListNode cur=newhead;
//        while(cur.next!=null){
//            if(cur.next.val==val){
//                cur.next=cur.next.next;
//            }
//            else{
//                cur=cur.next;
//            }
//        }
//        return newhead.next;
//    }
//}










/**删除排序链表中的重复元素
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public ListNode deleteDuplicates(ListNode head) {
//        if(head==null||head.next==null){
//            return head;
//        }
//        ListNode newhead=new ListNode(-1);
//        newhead.next=head;
//        ListNode cur=head;
//        ListNode perv=newhead;
//        while(cur!=null&&cur.next!=null){
//            if(cur.val==cur.next.val){
//                int val=cur.val;
//                while(cur.next!=null&&val==cur.next.val){
//                    cur=cur.next;
//                }
//                perv.next=cur;
//            }
//            else{
//                perv=cur;
//                cur=cur.next;
//            }
//        }
//        return newhead.next;
//    }
//}











/**删除链表中的节点
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//class Solution {
//    public void deleteNode(ListNode node) {
//        node.val=node.next.val;
//        node.next=node.next.next;
//    }
//}








/**相交链表
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
//public class Solution {
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        if(headB==null&&headA==null){
//            return null;
//        }
//        if(headA==null){
//            return headB;
//        }
//        if(headB==null){
//            return headA;
//        }
//        int len1=0;
//        int len2=0;
//        ListNode cura=headA;
//        ListNode curb=headB;
//        while(cura!=null){
//            len1++;
//            cura=cura.next;
//        }
//        while(curb!=null){
//            len2++;
//            curb=curb.next;
//        }
//        int len=len1-len2;
//        if(len<0){
//            len=len2-len1;
//            cura=headB;
//            curb=headA;
//        }
//        else{
//            cura=headA;
//            curb=headB;
//        }
//        while(len>0){
//            cura=cura.next;
//            len--;
//        }
//        while(cura!=curb){
//            cura=cura.next;
//            curb=curb.next;
//        }
//        return cura;
//    }
//}













/**回文链表
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class Solution {
//    public boolean isPalindrome(ListNode head) {
//        if(head==null){
//            return true;
//        }
//        ListNode slow=List(head);
//        ListNode fast=Data(slow);
//        ListNode newhead=head;
//        ListNode Head=fast;
//        while( Head!=null){
//            if(newhead.val!=Head.val){
//                return false;
//            }
//            newhead=newhead.next;
//            Head=Head.next;
//        }
//        return true;
//    }
//    public ListNode Data(ListNode head){
//        ListNode cur=head;
//        ListNode perv=null;
//        while(cur!=null){
//            ListNode curnext=cur.next;
//            cur.next=perv;
//            perv=cur;
//            cur=curnext;
//        }
//        return perv;
//    }
//    public ListNode List(ListNode head){
//        ListNode slow=head;
//        ListNode fast=head;
//        while(fast!=null&&fast.next!=null){
//            fast=fast.next.next;
//            slow=slow.next;
//        }
//        return slow;
//    }
//}














/**从尾到头打印链表
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//class Solution {
//    public int[] reversePrint(ListNode head) {
//        ListNode cur=head;
//        int count=0;
//        while(cur!=null){
//            count++;
//            cur=cur.next;
//        }
//        cur=head;
//        int[] ret=new int[count];
//        while(cur!=null){
//            ret[count-1]=cur.val;
//            cur=cur.next;
//            count--;
//        }
//        return ret;
//    }
//}









/**链表中倒数第k个节点
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//class Solution {
//    public ListNode getKthFromEnd(ListNode head, int k) {
//        if(head==null){
//            return null;
//        }
//        if(k<0){
//            return null;
//        }
//        ListNode slow=head;
//        ListNode fast=head;
//        while(k>1){
//            fast=fast.next;
//            k--;
//        }
//        while(fast.next!=null){
//            fast=fast.next;
//            slow=slow.next;
//        }
//        return slow;
//    }
//}









/**环形链表
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
//public class Solution {
//    public boolean hasCycle(ListNode head) {
//        if(head==null||head.next==null){
//            return false;
//        }
//        ListNode slow=head;
//        ListNode fast=head;
//        while(fast!=null&&fast.next!=null){
//            slow=slow.next;
//            fast=fast.next.next;
//            if(slow==fast){
//                return true;
//            }
//        }
//        return false;
//    }
//}










//搜索插入位置
//class Solution {
//    public int searchInsert(int[] nums, int target) {
//        int l=0;
//        int r=nums.length-1;
//        int ans=nums.length;
//        while(l<=r){
//            int m=(r+l)/2;
//            if(target<=nums[m]){
//                ans=m;
//                r=m-1;
//            }
//            else{
//                l=m+1;
//            }
//        }
//        return ans;
//    }
//}









// 第一个错误的版本
///* The isBadVersion API is defined in the parent class VersionControl.
//      boolean isBadVersion(int version); */
//
//public class Solution extends VersionControl {
//    public int firstBadVersion(int n) {
//        int l=1;
//        int r=n;
//        while(l<r){
//            int m=l+(r-l)/2;
//            if(isBadVersion(m)){
//                r=m;
//            }
//            else{
//                l=m+1;
//            }
//        }
//        return r;
//    }
//}








//二分查找
//class Solution {
//    public int search(int[] nums, int target) {
//        int slow=0;
//        int fast=nums.length-1;
//        while(slow<=fast){
//            int tmp=(slow+fast)/2;
//            if(nums[tmp]<target){
//                slow=tmp+1;
//            }
//            else if(nums[tmp]>target){
//                fast=tmp-1;
//            }
//            else {
//                return tmp;
//            }
//        }
//        return -1;
//    }
//}









//删除链表中重复的结点
//public class Solution {
//    public ListNode deleteDuplication(ListNode pHead) {
//        ListNode newpHead =new ListNode(-1);
//        ListNode cur=pHead;
//        newpHead.next=pHead;
//        ListNode perv=newpHead;
//        while(cur!=null&&cur.next!=null){
//            if(cur.val==cua.next.val){
//                int val=cur.val;
//                while(cur!=null&&val==cur.val){
//                    cur=cur.next;
//                }
//                prev.next=cur;
//            }
//            else{
//                prev=cur;
//                cur=cur.next;
//            }
//        }
//        return newpHead.next;
//    }
//}








/**从尾到头打印链表
 *    public class ListNode {
 *        int val;
 *        ListNode next = null;
 *
 *        ListNode(int val) {
 *            this.val = val;
 *        }
 *    }
 *
 */
//import java.util.ArrayList;
//public class Solution {
//    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
//        ArrayList<Integer> ret=new ArrayList<>();
//        if(listNode==null){
//            return ret;
//        }
//        ArrayList<Integer> list=new ArrayList<>();
//        while(listNode.next!=null){
//            list.add(listNode.val);
//            listNode=listNode.next;
//        }
//        list.add(listNode.val);
//        int len=list.size();
//        for(int i=len-1;i>=0;i--){
//            ret.add(list.get(i));
//        }
//        return ret;
//    }
//}